import java.util.*;
import java.io.*;
/*
试除法求约数
给定 n个正整数 ai，对于每个整数 ai，请你按照从小到大的顺序输出它的所有约数。

输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个整数 ai。

输出格式
输出共 n 行，其中第 i 行输出第 i 个整数 ai 的所有约数。

数据范围
1≤n≤100,2≤ai≤2×1e9

输入样例：
2
6
8

输出样例：
1 2 3 6
1 2 4 8
 */
//public class Main {
//    static ArrayList<Integer> divisors = new ArrayList<>();
//
//    static void getDivisors(int n) {
//        divisors.clear();
//        for (int i = 2; i <= n / i; i++) {
//            if (n % i == 0) {
//                divisors.add(i);
//                if (n != i * i) {
//                    divisors.add(n / i);
//                }
//            }
//        }
//        Collections.sort(divisors);
//    }
//
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//        while (n-- > 0) {
//            getDivisors(sc.nextInt());
//            for (int i : divisors) {
//                System.out.print(i + " ");
//            }
//        }
//    }
//}

/*
约数个数
给定 n 个正整数 ai，请你输出这些数的乘积的约数个数，答案对 1e9+7 取模。

输入格式
第一行包含整数n。
接下来 n 行，每行包含一个整数 ai。

输出格式
输出一个整数，表示所给正整数的乘积的约数个数，答案需对1e9+7 取模。

数据范围
1≤n≤100,1≤ai≤2×1e9

输入样例：
3
2
6
8

输出样例：
12
 */

//public class Main {
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//        HashMap<Integer, Integer> hash = new HashMap<>();
//        for (int i = 1; i <= n; i++) {
//            int a = sc.nextInt();
//            for (int j = 2; j <= a / j; j++) {
//                while (a % j == 0) {
//                    hash.put(j, hash.getOrDefault(j, 0) + 1);
//                    a = a / j;
//                }
//            }
//            if (a > 1) hash.put(a, hash.getOrDefault(a, 0) + 1);
//        }
//        long res = 1;
//        for (Map.Entry<Integer, Integer> entry : hash.entrySet()) {
//            res = res * (entry.getValue() + 1) % 1000000007;
//        }
//        System.out.println(res);
//    }
//}


/*
约数之和
给定 n 个正整数 ai，请你输出这些数的乘积的约数之和，答案对 1e9+7 取模。

输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个整数 ai。

输出格式
输出一个整数，表示所给正整数的乘积的约数之和，答案需对 1e9+7 取模。

数据范围
1≤n≤100,1≤ai≤2×1e9

输入样例：
3
2
6
8

输出样例：
252
 */
//public class Main {
//    //计算 1+n+n^2+...+n^f
//    static long factorial(int n, int f) {
//        long sum = 0;
//        long fac = 1;
//        for (int i = 0; i <= f; i++) {
//            sum += fac;
//            fac *= n;
//        }
//        return sum % 1000000007;
//    }
//
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//        HashMap<Integer, Integer> hash = new HashMap<>();
//        for (int i = 1; i <= n; i++) {
//            int a = sc.nextInt();
//            for (int j = 2; j <= a / j; j++) {
//                while (a % j == 0) {
//                    hash.put(j, hash.getOrDefault(j, 0) + 1);
//                    a = a / j;
//                }
//            }
//            if (a > 1) hash.put(a, hash.getOrDefault(a, 0) + 1);
//        }
//        long res = 1;
//        for (Map.Entry<Integer, Integer> entry : hash.entrySet()) {
//            res = (res * factorial(entry.getKey(), entry.getValue())) % 1000000007;
//        }
//        System.out.println(res);
//    }
//}

/*
最大公约数
给定 n 对正整数ai,bi，请你求出每对数的最大公约数。

输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个整数对 ai,bi。

输出格式
输出共 n 行，每行输出一个整数对的最大公约数。

数据范围
1≤n≤1e5,
1≤ai,bi≤2×1e9

输入样例：
2
3 6
4 6

输出样例：
3
2
 */
//public class Main {
//    static int gcd(int a, int b) {
//        return b != 0 ? gcd(b, a % b) : a;
//    }
//
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//        while (n-- > 0) {
//            System.out.println(gcd(sc.nextInt(), sc.nextInt()));
//        }
//    }
//}

/*
扩展欧几里得算法

给定 n 对正整数 a_i, b_i，对于每对数，求出一组 x_i, y_i，使其满足 a_i × x_i + b_i × y_i = gcd(a_i, b_i)。

输入格式
第一行包含整数 n。
接下来 n 行，每行包含两个整数 a_i, b_i。

输出格式
输出共 n 行，对于每组 a_i, b_i，求出一组满足条件的 x_i, y_i，每组结果占一行。
本题答案不唯一，输出任意满足条件的 x_i, y_i 均可。

数据范围
1 ≤ a_i, b_i ≤ 2 × 10^9

输入样例：
2
4 6
8 18

输出样例：
1 1
-2 1
 */
//public class Main {
//    // 使用一个类来包装 x 和 y
//    static class Result {
//        int x, y;
//    }
//
//    static int exGcd(int a, int b, Result result) {
//        if (b == 0) {
//            result.x = 1;
//            result.y = 0;
//            return a;
//        }
//        int d = exGcd(b, a % b, result);
//        int temp = result.y;
//        result.y = result.x - a / b * result.y;
//        result.x = temp;
//        return d;
//    }
//
//    public static void main(String[] args) throws IOException {
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
//        int n = Integer.parseInt(br.readLine());
//        for (int i = 1; i <= n; i++) {
//            String[] input = br.readLine().split(" ");
//            int a = Integer.parseInt(input[0]);
//            int b = Integer.parseInt(input[1]);
//            Result result = new Result();
//            exGcd(a, b, result);
//            pw.println(result.x + " " + result.y);
//        }
//        pw.flush();
//    }
//}

/*
线性同余方程

给定 n 组数据 a_i, b_i, m_i，对于每组数求出一个 x_i，使其满足 a_i × x_i ≡ b_i (mod m_i)，如果无解则输出 impossible。

输入格式
第一行包含整数 n。
接下来 n 行，每行包含一组数据 a_i, b_i, m_i。

输出格式
输出共 n 行，每组数据输出一个整数表示一个满足条件的 x_i，如果无解则输出 impossible。
每组数据结果占一行，结果可能不唯一，输出任意一个满足条件的结果均可。
输出答案必须在 int 范围之内。

数据范围
1 ≤ n ≤ 10^5
1 ≤ a_i, b_i, m_i ≤ 2 × 10^9

输入样例：
2
2 3 6
4 3 5

输出样例：
impossible
-3
 */
public class Main {
    // 使用一个类来包装 x 和 y
    static class Result {
        int x, y;
    }

    static int exGcd(int a, int b, Result result) {
        if (b == 0) {
            result.x = 1;
            result.y = 0;
            return a;
        }
        int d = exGcd(b, a % b, result);
        int temp = result.y;
        result.y = result.x - a / b * result.y;
        result.x = temp;
        return d;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        for (int i = 1; i <= n; i++) {
            String[] input = br.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            int m = Integer.parseInt(input[2]);
            Result result = new Result();
            int d = exGcd(a, m, result);
            if (b % d != 0) System.out.println("impossible");
            else pw.println(result.x * (b / d) % m);
        }
        pw.flush();
    }
}
